1. Field of the Invention
The present invention relates to techniques of retaining security of a computer network, and more particularly to encryption techniques using an elliptic curve.
2. Description of the Related Art
Elliptic curve encryption is public key cryptography independently invented by V. Miller and N. Koblitz.
The public key cryptosystem has been developed in order to eliminate disadvantages of a common key cryptosystem, the disadvantages being the security which may possibly be lowered at the stage when a private key which is kept secret from third parties is shared by two partners exchanging enciphered information. In this public key cryptosystem, a pair of a private and a public key is used. The private key secret from third parties belongs to a particular individual, and the public key is obtained through arithmetic operation of the private key and made public to third parties.
One feature of this public key cryptosystem resides in that a text enciphered by the public key of a particular person cannot be deciphered unless the private key (paired with the public key) of the person is used. This feature can be utilized when a text is transmitted to a partner while the text is kept secret from third parties. For example, when Mr. A transmits a text to Mr. B, the text enciphered by using the public key of Mr. B is transmitted. The enciphered text can be deciphered only with the private key of Mr. B paired with the public key so that only Mr. B can recover the original plain text.
A text enciphered with the private key of a particular person can be verified, by using the public key paired with the private key of the person, as to whether or not the text was enciphered by the secret key. This feature can be applied to digital signature. The digital signature is data obtained through arithmetic operation of a text to be signed and through encipher with the private key of the signer. For example, verification of the digital signature of Mr. A can be made depending upon whether or not the data obtained through decipher of the digital signature with the public key of Mr. A is coincident with the data obtained through arithmetic operation of a text to be signed and through encipher with the private key of the signer. If coincident, it can be verified that the digital signature is a correct signature made by Mr. A and that the text with the digital signature was not illegally altered. This feature can therefore be applied to identification of a particular person and prevention of illegal alteration on a network such as the Internet. Verification of a correct signature can be applied to prevent a hostile pretender from purchasing some goods. Verification of no alteration of a text can be applied to prevent alteration of a price entered in a contract note or a receipt.
From the viewpoint of security, requirements for the public key cryptosystem are that it is practically impossible to find a private key from a paired public key made public to third parties. Other requirements for the public key cryptosystem which fundamentally takes a longer encipher and decipher time than a private key cryptosystem are a shorter encipher and decipher time. As the techniques of the public key cryptosystem satisfying these to contradictory requirements of security and speed, an elliptic curve encryption has been paid much attention, which is better than conventional RSA and ElGamal cryptosystems.
An elliptic curve is represented by a standard formula y2=x3+ax+b (4a+27bxe2x89xa00) of an elliptic curve in a finite field having a characteristic of 5 or higher. If a point of infinity is added to this curve, the Abelian group is established. The Abelian operation is represented by a symbol xe2x80x9c+xe2x80x9d.
A typical elliptic curve used for encryption is represented by the following standard forms of Weierstrass.
0: Unit element (a point of infinity on a two-dimensional projective plane of an elliptic curve).
0+0=0
2) (x, y)+0=(x, y)
3) (x, y)+(x, xe2x88x92y)=0
4) Commutativity (x1, y1)+(x2, y2)=(x2, y2)+(x1, y1)
5) Addition (x3, y3)=(x1, y1)+(x2, y2) x3=xcex2xe2x88x92x1xe2x88x92x2; y3=xcex(x1xe2x88x92x3)xe2x88x92y1; xcex=(y2xe2x88x92y1)/(x2xe2x88x92x1)
6) Doubling (x3, y3)=(x1, y1)+(x1, y1)=2(x1, y1) x3=xcex2xe2x88x922*x1; y3=xcex(x1xe2x88x92y3)xe2x88x92y1; xcex=(3*x12=a)/(2*y1)
An elliptic curve cryptograph uses an elliptic curve in a finite field and a set of points constituting the finite filed.
As the finite field, a set Fp of remainders of integers congruent modulo of a prime p is used.
Fp={0, 1, . . . , pxe2x88x921}
The order of a finite field is the number of elements of the finite field. The order of an elliptic curve is the number of points on an elliptic curve.
A result of s-time addition of P (p+ . . . +P) is called an s-multiple point of P, and an operation of obtaining the s-multiple point of P is represented by sP.
The order of a point P on an elliptic curve is n which satisfies nP=0, 1 less than =m less than n, and mpxe2x89xa00.
Keys of the elliptic curve cryptograph include the following elliptic curve, base point, public key, and private key.
Coefficients of an elliptic curve are a and b.
Base point: a point P having a prime as the order.
Private key: finite field element d.
Public key: a point of private-key-multiplication of the base point Q (Q=dP).
An elliptic curve, base point, and public key are public information. The public key and private key are different for each user, whereas the elliptic curve and base point are common to each user.
Data encipher, data decipher, digital signature generation, and digital signature verification respectively of the elliptic curve encryption uses a sR operation of an arbitrary point R. This operation can be executed by a combination of the above-described addition and doubling. The above-described addition arithmetic and doubling each require to perform a division once. However, it takes a very long time to perform a division in a finite field. A method of avoiding a division in the finite field has been desired.
According to the document of D. V. Chudnovsky, G. V. Chudnovsky xe2x80x9cSequences of Numbers Generated by Addition in Formal Groups and New and New Primality and Factorization Testsxe2x80x9d, Advances in Applied Mathematics, 7, 385-434, 1986, formulas of the addition and doubling are derived in a projective space. These formulas will be described in the following.
Addition:
[X3, Y3, Z3]=[X1, Y1, Z1]+[X2, Y2, Z2]
X3=xe2x88x92(U1+U2)P2+R2
xe2x80x832Y3=R(xe2x88x922R2+3P2(U1+U2))xe2x88x92P3(S1+S2)
Z3=Z1Z2P
U1=X1(Z2)2; U2=X2(Z1)2; S1=Y1(Z2)3
S2=Y2(Z1)3
P=U2xe2x88x92U1; R=S2xe2x88x92S1
Doubling:
[X3, Y3, Z3]=2[X1, Y1, Z1]
X=T
Y=xe2x88x928((Y1)2)2+M(Sxe2x88x92T)
Z=2Y1Z1
S=4X1(Y1)2; M=3(X1)2+a((Z1)2)2; T=xe2x88x922S+M2
M=3(X1xe2x88x92(Z1)2(X1+(Z1)2 if a=xe2x88x923
M=3(X1)2 if a=0
The X1, Y1, and Z1 are finite field elements whose data can be expressed by a multiple-precision integer (larger than 2160)
Multiple-precision multiplication modulo arithmetic generally takes a longer time than multiple-precision addition subtraction. Therefore, a calculation time can be evaluated from the multiplication modulo arithmetic. The above-cited document describes that the addition arithmetic requires to perform a multiplication modulo operation 16 times and the doubling requires to perform it 10 times. It also describes that if the coefficient a of an elliptic curve is a=xe2x88x923, it is required to perform the multiplication modulo operation 8 times, and if a=0, it is required to perform it 8 times.
The document further describes a method using an expression of [X1, Y1, Z1, (Z1)2, (Z1)3] which is described in the following.
Addition arithmetic:
[X1, Y1, Z1, (Z1)2, (Z1)3]=[X1, Y1, Z1, (Z1)2, (Z1)3]+[X2, Y2, Z2, (Z2)2, (Z2)3]
Doubling:
[X3, Y3, Z3, (Z3)2, (Z3)3]=2[X1, Y1, Z1, (Z1)2, (Z1)3]
The document describes that the addition arithmetic requires to perform the multiplication modulo operation 14 times and the doubling requires to perform it 11 times.
The addition arithmetic can be performed at high speed by  less than Chudnovsky Formulas 2 greater than , whereas the doubling can be performed at high speed by  less than Chudnovsky Formulas 1 greater than .
As an example of the multiple-precision multiplication modulo arithmetic, Montgomery modulo arithmetic is known which is described in the document of A. Menezes, P. Oorschot, S. Vanstone, xe2x80x9cHandbook of Applied Cryptographyxe2x80x9d, CRC Press, p. 600 (1996), Section 14.3 Multiple-precision modular arithmetic.
The Montgomery modulo arithmetic described in this document will be described.
Input:
p=(pnxe2x88x921, . . . , p2, p1); gcd(p, b)=1; R=bn;
pxe2x80x2=xe2x88x921/p mod b; T=(t2nxe2x88x921, . . . , t1, t0) less than pR;
b=2w 
p is a modulo by which an integer is divided to obtain a remainder. 0 less than =pi less than b. 0 less than =ti less than b. w is a positive integer. T is a multiplication result of integers x and y which is smaller than p.
An output is assumed to be T/R (mod p).
Step 1: A←T
Step 2: The following Steps 2.1 and 2.2 are executed from i=0 to i=(nxe2x88x921).
Step 2.1: ui←aipxe2x80x2 mod b
Step 2.2: A←A+uipbi 
Step 3: A←A/bn 
Step 4: If A greater than =p, then A←Axe2x88x92p
Step 5: A is an output.
An elliptic curve used for the elliptic curve encryption is expressed by an elliptic curve y2=x2+ax+b which uses as the definition field a prime field Fp having a prime p as its order. In order to form a perfect elliptic curve, it is necessary to set the parameters a and b which have prime factors r having a large order #E(Fp) of an elliptic curve, where
#E(Fp)=kr, k is a small integer, and r is a large prime.
A method of setting parameters of an elliptic curve having primes with a large order is described in the document of Henri Cohen, xe2x80x9cA Course in Computational Algebraic Number Theoryxe2x80x9d, GTM138, Springer (1993), p.464, Atkin""s Test.
As a primality test used when the prime p is generated, a Miller-Rabin primality test is widely used which is described in the document of A. Menezes, P. Oorschot, S. Vanstone, xe2x80x9cHandbook of Applied Cryptographyxe2x80x9d, CRC Press, p. 139 (1996), Section 4.1.3.
Elliptic curve cryptograph using specific primes are described in U.S. Pat. No. 5,271,061 and U.S. Pat. No. 5,463,690. These patents disclose techniques of using the prime p in the form of xe2x80x9cp=2exe2x88x92a; e is a positive integer; and a less than 232 or a=1xe2x80x9d in the elliptic curve encryption having as its definition field a finite field Fq with q=pk, i.e., a finite field of characteristic p. An operation of obtaining an s-multiple point of a point P is similar to an exponentiation modulo operation of an integer of a raised to a power of e. As a high speed exponent operation, a sliding-window method is known which is described in the document of A. Menezes, P. Oorschot, S. Vanstone, xe2x80x9cHandbook of Applied Cryptographyxe2x80x9d, CRC Press, p. 616 (1996), Section 14.6.1 (ii), xe2x80x9cSliding-window exponentiationxe2x80x9d.
Both  less than Chudnovsky Formulas 1 greater than  and  less than Chudnovsky Formulas 2 greater than  are not satisfactory for high speed operations. The inventors consider that an operation method is desired which provides an efficiency of  less than Chudnovsky Formulas 2 greater than  for the addition and an efficiency of  less than Chudnovsky Formulas 1 greater than  for the doubling.
In order to further speed up a calculation time, it is necessary to speed up the multiplication modulo operation used in  less than Chudnovsky Formulas 1 greater than  and  less than Chudnovsky Formulas 2 greater than .
In order to solve the above-described problems, the following means are provided in order to use a high speed [X1, Y1, Z1, (Z1)2, (Z1)3] for the addition and a high speed [X1, Y1, Z1] for the doubling.
(1) Addition: execute [X3, Y3, Z3]=[X1, Y1, Z1, (Z1)2, (Z1)3]+[X2, Y2, Z2].
(2) A doubling point calculation is executed by a conventional [X3, Y3, Z3]=2[X1, Y1, Z1] and an addition operation is executed by [X3, Y3, Z3]=[X1, Y1, Z1, (Z1)2, (Z1)3]+[X2, Y2, Z2].
It is also required to speed up the multiplication modulo operation. The Montgomery multiplication modulo operation is speeded up by using the following forms of the definition order (prime).
(3) The multiplication modulo operation is executed at high speed by using a prime having a form of p=Abn+B (0 less than A less than 2w; 0 less than B less than 2w; b=2w; and w, A, b, n and B are positive integers).